//这是int改为size_t，去掉打印语句的版本
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// DFS 函数，寻找从 start 到 end 的所有路径(DFS算法确认无误)
void dfs(size_t start, size_t end, const vector<vector<size_t>>& roadlength, vector<bool>& visited, vector<size_t>& current_path, vector<vector<size_t>>& all_paths) {
    visited[start] = true; // 标记当前节点为已访问
    current_path.push_back(start); // 将当前节点加入路径

    if (start == end) {
        all_paths.push_back(current_path); // 找到一条路径，保存到 all_paths 中
    } else {
        // 遍历所有邻接节点
        for (size_t i = 0; i < roadlength.size(); i++) {
            if (roadlength[start][i] != INT_MAX && !visited[i]) { // 如果道路存在且未访问
                vector<size_t> new_path = current_path;
                dfs(i, end, roadlength, visited, new_path, all_paths); // 递归搜索
            }
        }
    }

    // 回溯
    if (!current_path.empty()) {
        current_path.pop_back();
    }
    visited[start] = false;
}

// 检测当前车辆路径组合是否会导致堵车

struct Event {
    size_t time;
    size_t u; // 起始节点
    size_t v; // 结束节点
    bool enter; // 进入路段（true）还是离开路段（false）
    // 重载比较运算符，使优先队列按时间升序排列
    bool operator>(const Event& other) const {
        return time > other.time;
    }
};

bool checkTraffic(const vector<vector<size_t>>& combination,
                  const vector<vector<size_t>>& roadlength,
                  const vector<vector<size_t>>& restrictions) {
    
    
    
    // 创建优先队列，存储事件
    priority_queue<Event, vector<Event>, greater<Event>> eventQueue;

    // 初始化事件队列
    for (const vector<size_t>& path : combination) {
        size_t current_time = 0;
        for (size_t i = 1; i < path.size(); ++i) {
            size_t u = path[i - 1];
            size_t v = path[i];
            size_t length = roadlength[u][v];
            eventQueue.push({current_time, u, v, true}); // 进入事件
            eventQueue.push({current_time + length, u, v, false}); // 离开事件
            current_time += length;
        }
    }

    // 维护当前每条道路的流量
    vector<vector<size_t>> current_flow(roadlength.size(),
                                               vector<size_t>(roadlength.size(), 0));

    while (!eventQueue.empty()) {
        size_t current_time = eventQueue.top().time;
        vector<Event> same_time_events;
        // 取出所有时间等于current_time的事件
        while (!eventQueue.empty() && eventQueue.top().time == current_time) {
            same_time_events.push_back(eventQueue.top());
            eventQueue.pop();
        }
        // 先处理离开事件
        for (Event& event : same_time_events) {
            if (!event.enter) {
                if (current_flow[event.u][event.v] > 0) {
                    current_flow[event.u][event.v]--;
                    current_flow[event.v][event.u]--;
                }
            }
        }
        // 再处理进入事件
        for (Event& event : same_time_events) {
            if (event.enter) {
                current_flow[event.u][event.v]++;
                current_flow[event.v][event.u]++;
                if (current_flow[event.u][event.v] > restrictions[event.u][event.v]) {
                    return false; // 堵车
                }
            }
        }
    }
    
    // 所有事件处理完毕，没有堵车
    return true;
}

// 计算当前组合的总路径长度
size_t calculateTotalLength(const vector<vector<size_t>>& combination, const vector<vector<size_t>>& roadlength) {
    size_t total_length = 0;
    for (const vector<size_t>& path : combination) {
        for (size_t i = 1; i < path.size(); i++) {
            size_t u = path[i - 1];
            size_t v = path[i];
            total_length += roadlength[u][v];
        }
    }
    return total_length;
}

// 遍历所有车辆路径组合的函数
void traverseCombinations(const vector<vector<vector<size_t>>>& all_cars_paths, size_t car_index, vector<vector<size_t>>& current_combination, vector<vector<vector<size_t>>>& all_combinations) {
    // 如果已经处理完所有车辆，保存当前组合
    if (car_index == all_cars_paths.size()) {
        all_combinations.push_back(current_combination);
        return;
    }

    // 遍历当前车辆的所有路径方案
    for (const vector<size_t>& path : all_cars_paths[car_index]) {
        current_combination.push_back(path); // 选择当前路径方案
        traverseCombinations(all_cars_paths, car_index + 1, current_combination, all_combinations); // 递归处理下一辆车
        current_combination.pop_back(); // 回溯，撤销选择
    }
}

// 找到不堵车且总路径长度最短的组合
void findBestCombination(const vector<vector<vector<size_t>>>& all_cars_paths, const vector<vector<size_t>>& roadlength, const vector<vector<size_t>>& restrictions) {
    vector<vector<size_t>> best_combination; // 存储最短组合
    size_t min_total_length = INT_MAX; // 记录最短组合的总路径长度

    
    // 遍历所有车辆路径组合
    vector<vector<size_t>> current_combination;
    vector<vector<vector<size_t>>> all_combinations;
    traverseCombinations(all_cars_paths, 0, current_combination, all_combinations);

    for (const vector<vector<size_t>>& combination : all_combinations) {
        // 检查是否堵车
        

        if (checkTraffic(combination, roadlength, restrictions)) {
            // 计算总路径长度
            size_t total_length = calculateTotalLength(combination, roadlength);
            
            // 如果总路径长度更短，更新最短组合
            if (total_length < min_total_length) {
                min_total_length = total_length;
                best_combination = combination;
            }
        }
    }

    // 输出最短组合
    if (!best_combination.empty()) {
        cout << "Best combination (total length: " << min_total_length << "):" << endl;
        for (size_t i = 0; i < best_combination.size(); i++) {
            cout << "Car " << i + 1 << " path: ";
            for (size_t node : best_combination[i]) {
                cout << node + 1 << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No valid combination found!" << endl;
    }
}

int main() {
    size_t N, M;
    cin >> N >> M;

    // 动态分配二维数组
    vector<vector<size_t>> roadlength(N, vector<size_t>(N, INT_MAX)); // 存储道路长度
    vector<vector<size_t>> restrictions(N, vector<size_t>(N)); // 存储道路的流量限制
    vector<vector<size_t>> cars(M, vector<size_t>(2)); // 存储每辆车的起点和终点

    // 读取道路长度
    for (size_t i = 0; i < N; i++) {
        for (size_t j = 0; j < N; j++) {
            cin >> roadlength[i][j];
            if (roadlength[i][j] == 0 && i != j) {
                roadlength[i][j] = INT_MAX; // 如果道路长度为 0，则距离为无穷大
            }
        }
    }

    // 读取道路的流量限制
    for (size_t i = 0; i < N; i++) {
        for (size_t j = 0; j < N; j++) {
            cin >> restrictions[i][j];
        }
    }

    // 读取每辆车的起点和终点
    for (size_t i = 0; i < M; i++) {
        cin >> cars[i][0] >> cars[i][1];
        cars[i][0]--; // 将输入的起点和终点转换为从 0 开始的索引
        cars[i][1]--;
    }

    // 存储每辆车的所有路径
    vector<vector<vector<size_t>>> all_cars_paths(M); // 每辆车的所有路径

    // 为每辆车找到所有路径
    for (size_t i = 0; i < M; i++) {
        size_t start = cars[i][0];
        size_t end = cars[i][1];
        vector<bool> visited(N, false); // 记录节点是否被访问
        vector<size_t> current_path; // 记录当前路径
        vector<vector<size_t>> all_paths; // 存储所有路径

        dfs(start, end, roadlength, visited, current_path, all_paths);

        all_cars_paths[i] = all_paths; // 保存当前车辆的所有路径
    }
    
    // 找到不堵车且总路径长度最短的组合
    findBestCombination(all_cars_paths, roadlength, restrictions);

    return 0;
}